package leetcode_1_20;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class lengthOfLongestSubstring_3 {
    /**
     * 3，无重复字符的最长子串
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int maxLen=0;   //最大长度
        int len=0;           //实时长度
        List arr=new ArrayList(){};   //使用集合表示子串，便于处理
        //chars()方法转换字符串至Integer流
        //显示使用mapToObj()方法进行类型转换为char。
        List<Character> list=s.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.toList());
        for( char c : list ){
            //判断该字符是否在子串中存在
            if( arr.contains(c) ){
                //发现包含该元素，则存储该子串的长度
                if( len >= arr.size() ) {  //判断大于上一个子串长度则重置子串和len
                    //并且查找该字符的位置，从该字符下一位开始重置子串
                    arr = arr.subList(arr.indexOf(c)+1,arr.size());
                    arr.add(c);
                    len=arr.size();
                } else {            //小于上一个子串长度
                    arr.clear();
                    arr.add(c);
                    len = 1;      //则重置len
                }
            }else{  //不存在
                arr.add(c);    //加入该字符到子串中
                len++;          //不存在则len++
                if(len>maxLen) maxLen = len;   //当len比maxLen大时直接替换
            }
        }
        return maxLen;
    }

    /**
     * 3.1，改进高效解法，维护一个int数组，代表字符int值
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        int maxLen=0,start=0,end=0;
        char[] chars=s.toCharArray();  //将s转化为char数组遍历
        int charMap[]=new int[128];  //范围 0~128 包含所有字符的ascii值
        Arrays.fill(charMap,0);        //全部填充0，用0和1来维护该数组
        for (char c:chars) {
            // 循环判断是否和前面子串冲突
            while (0 != charMap[ chars[end] ]){   //charMap[ chars[end] =0 则不冲突
                //如果冲突，则charMap [chars[start]] 开始进位变为0，循环判断，直到不冲突
                charMap [chars[start++]]=0;
            }
            //实时根据子串的大小更新maxLen
            maxLen=maxLen > end-start+1 ?  maxLen: end-start+1;
            charMap[chars[end]]=1;  //不冲突则变为1
            end++;
        }
        return maxLen;
    }

    public static void main(String[] args) {
         System.out.println(lengthOfLongestSubstring1("pwwkew"));
    }

}
